<?php
/**
 * @title 410. 分割数组的最大值 - 平均值
 * @author start2004
 */

class Solution {

    /**
     * @param Integer[] $nums
     * @param Integer $m
     * @return Integer
     */
    function splitArray($nums, $m) {
        /**
         * @since 2020-10-13 数量
         */
        $len = count($nums);

        /**
         * @since 2020-10-13 总和
         */
        $sum = array_sum($nums);
        echo "sum={$sum}, len={$len}", PHP_EOL;

        /**
         * @since 2020-10-13 缓存
         */
        $this->dps = [];
        $this->nums = $nums;

        /**
         * @since 2020-10-13 最小最大值
         */
        $min = self::find($m, 0, $len, $sum);

        /**
         * @return
         */
        return $min;
    }

    /**
     * @title
     * @author start2004
     * @since 2020-10-13 Created
     *
     * @param int $m
     * @param int $left
     * @param int $len
     * @param int $sum
     * @return mixed|null
     */
    public function find($m = 0, $left = 0, $len = 0, $sum = 0){
        $key = "{$m}-{$left}-{$len}-{$sum}";
        if(isset($this->dps[$key])){
            return $this->dps[$key];
        } else {}

        /**
         * @since 2020-10-13 所有值
         */
        if($m == 1){
            $max = $sum;
        } elseif($m == $len){
            /**
             * @since 2020-10-13 子数组数量和数组数量一致, 即求最大值
             */
            $max = $this->nums[$left];
            for ($i=1; $i<$len; $i++){
                $max = max($max, $this->nums[$left+$i]);
            }
        } else {
            /**
             * @since 2020-10-13 最大值
             */
            $max = null;

            /**
             * @since 2020-10-13 平均值, 最理想的最大值
             */
            $avg = ceil($sum/$m);

            /**
             * @since 2020-10-13 第一个子数组长度从1到len-m+1
             * @since 2020-10-13 接近平均值
             */
            $s = 0;
            for($i=1, $iMax=$len-$m+1; $i<=$iMax; $i++){
                $num = $this->nums[$i+$left-1];
                $s += $num;

                /**
                 * @since 2020-10-14 小于max, 贪心继续
                 */
                if($max !== null AND $s>=$max){
                    break;
                } else {}

                /**
                 * @since 2020-10-13 小于平均值, 继续
                 */
                if($s < $avg){
                } elseif($s == $avg) {
                    /**
                     * @since 2020-10-13 等于平均值, 递归, break
                     * @since 2020-10-14 s==avg, 后续最理想情况的, 也是平均值, 但这个avg是进1
                     * @since 2020-10-14 nums=[4,3,3,3], m=2, 平均值avg=6.5=7, 如果抛弃s, 会导致返回6, 实际是7
                     */
                    // $max = self::find($m-1, $left+$i, $len-$i, $sum-$s);
                    $max = max($s, self::find($m-1, $left+$i, $len-$i, $sum-$s));
                    // break;
                } else {
                    /**
                     * @since 2020-10-13 大于平均值
                     */
                    $max1 = max($s, self::find($m-1, $left+$i, $len-$i, $sum-$s));

                    /**
                     * @since 2020-10-13 存在上一个子数组, 小于平均值
                     */
                    if($i > 1){
                        $s2 = $s-$num;
                        $i2 = $i-1;
                        $max2 = max($s2, self::find($m-1, $left+$i2, $len-$i2, $sum-$s2));
                        $max = min($max1, $max2);
                    } else {
                        $max = $max1;
                    }

                    // echo ">, s={$s}, avg={$avg}, left={$left}, num=", $this->nums[$left] ,", i={$i}, m={$m}, max={$max1}", PHP_EOL;
                    // if($i>1){
                    //     echo ">, s={$s2}, avg={$avg}, left={$left}, num=", $this->nums[$left] ,", i={$i2}, m={$m}, max={$max2}", PHP_EOL, PHP_EOL;
                    // } else {}
                    // break;
                }
            }

            /**
             * @since 2020-10-14 出现null, nums=[2,2,10], m=2, avg=7, 第一个子数组最多2个长度, 怎么加也不会超过avg
             */
            if($max === null){
                // echo "max is null, ", PHP_EOL;
                $max = 0;
                for($j=1; $j<=$m-1; $j++, $i++){
                    $max = max($max, $this->nums[$i+$left-1]);
                }
            } else {}
        }

        /**
         * @return
         */
        $this->dps[$key] = $max;
        return $max;
    }
}




/**
 * @url http://127.0.0.1/leetcode/202007/2020.07.25_2.php
 */
$datas = [
    [[1,60,25,25,1,1,30,110,40,70,37], 4], // 140
    // [[5,2,4,1,3,6,0], 2], // 0
    // [[3,2,3,1,2,4,1,1,10,11,2], 8], // 11
    // [[3,2,3,1,2,4,5,5,6,7,7,8,2,3,1,1,1,10,11,5,6,2,4,7,8,5,6], 20], // 11
    // [[7,2,5,10,8], 5], // 10
    // [[7,2,5,10,8], 2], // 18
    // [[5334,6299,4199,9663,8945,3566,9509,3124,6026,6250,7475,5420,9201,9501,38,5897,4411,6638,9845,161,9563,8854,3731,5564,5331,4294,3275,1972,1521,2377,3701,6462,6778,187,9778,758,550,7510,6225,8691,3666,4622,9722,8011,7247,575,5431,4777,4032,8682,5888,8047,3562,9462,6501,7855,505,4675,6973,493,1374,3227,1244,7364,2298,3244,8627,5102,6375,8653,1820,3857,7195,7830,4461,7821,5037,2918,4279,2791,1500,9858,6915,5156,970,1471,5296,1688,578,7266,4182,1430,4985,5730,7941,3880,607,8776,1348,2974,1094,6733,5177,4975,5421,8190,8255,9112,8651,2797,335,8677,3754,893,1818,8479,5875,1695,8295,7993,7037,8546,7906,4102,7279,1407,2462,4425,2148,2925,3903,5447,5893,3534,3663,8307,8679,8474,1202,3474,2961,1149,7451,4279,7875,5692,6186,8109,7763,7798,2250,2969,7974,9781,7741,4914,5446,1861,8914,2544,5683,8952,6745,4870,1848,7887,6448,7873,128,3281,794,1965,7036,8094,1211,9450,6981,4244,2418,8610,8681,2402,2904,7712,3252,5029,3004,5526,6965,8866,2764,600,631,9075,2631,3411,2737,2328,652,494,6556,9391,4517,8934,8892,4561,9331,1386,4636,9627,5435,9272,110,413,9706,5470,5008,1706,7045,9648,7505,6968,7509,3120,7869,6776,6434,7994,5441,288,492,1617,3274,7019,5575,6664,6056,7069,1996,9581,3103,9266,2554,7471,4251,4320,4749,649,2617,3018,4332,415,2243,1924,69,5902,3602,2925,6542,345,4657,9034,8977,6799,8397,1187,3678,4921,6518,851,6941,6920,259,4503,2637,7438,3893,5042,8552,6661,5043,9555,9095,4123,142,1446,8047,6234,1199,8848,5656,1910,3430,2843,8043,9156,7838,2332,9634,2410,2958,3431,4270,1420,4227,7712,6648,1607,1575,3741,1493,7770,3018,5398,6215,8601,6244,7551,2587,2254,3607,1147,5184,9173,8680,8610,1597,1763,7914,3441,7006,1318,7044,7267,8206,9684,4814,9748,4497,2239],9], // 194890
];

include_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof();
foreach ($datas as $data){
    // var_dump($data);

    $obj = new Solution();
    $result = $obj->splitArray($data[0], $data[1]);
    var_dump($result);
    echo str_repeat("<br>", 3);
}
$xhprof->end();
